

//LCR 114.火星词典
class Solution {
public:
    string alienOrder(vector<string>& words) {
        //使用拓扑排序,通过将每个字符串进行对比就可以知道所有已知字符的大小关系
        //这样就能构建出图,如果是有向无环图就说明字符的大小关系成立,否则不成立
        vector<vector<char>> ch;  //存储字符之间的关系,其中0下标字符小于1下标字符
        int n=words.size();
        for(int i=0;i<n;i++)
        {    
            for(int j=i+1;j<n;j++)
            {
                string& s1=words[i];
                string& s2=words[j];
                int sz1=s1.size(),sz2=s2.size();
                int pos1=0,pos2=0;
                while(pos1<sz1&&pos2<sz2&&s1[pos1]==s2[pos2]) pos1++,pos2++;
                if(pos2==sz2&&pos1!=sz1) return {};  //如果s2走完了,s1还没走完这种情况是不应该的
                if(pos1!=sz1) ch.push_back({s1[pos1],s2[pos2]});
            }  
        }
        //此时所有的比较结果都已经存储起来了
        vector<int> m(26); //存储每一个字符前面还有多少比他小的
        vector<vector<int>> ln(26);  //记录每一个字符后面还有多少比他大的
        for(auto& tmp:ch)
        {
            m[tmp[1]-'a']++;
            ln[tmp[0]-'a'].push_back(tmp[1]-'a');
        }

        int count[26],num=0;  //记录所有已经出现的字符
        for(auto& str:words)
            for(auto& ch:str) 
                if(++count[ch-'a']==1) num++;

        queue<int> q;  //记录前面已经没有比他大的位置
        string ret;   //记录答案
        for(int i=0;i<26;i++)
            if(m[i]==0&&count[i]) q.push(i);
        while(!q.empty())
        {
            int sz=q.size();
            for(int k=0;k<sz;k++)
            {   
                int x = q.front();
                ret.push_back('a'+x);
                q.pop();
                auto& tmp=ln[x];
                for(auto& a:tmp)
                    if(--m[a]==0) q.push(a);
            }
        }
        
        return num==ret.size()?ret:"";  //比较返回的字符串是不是包含全部已经出现的字符
    }
};